#include<iostream>
#include<stack>
using namespace std;

bool PrecedThan(char c1, char c2)
{
    return ('*' == c1 || '/' == c1) &&
           ('+' == c2 || '-' == c2);
}

void InfixToSuffix(char const* infix, char* suffix)
{
    char const* pExpr = infix;
    char* pSuff = suffix;
    
    stack<char> stkOprt;
    while ('\0' != *pExpr)
    {
        if ('0' <= *pExpr && *pExpr <= '9')
        {
            *pSuff++ = *pExpr;
        }
        else
        {
            char ch;
            
            switch (*pExpr)
            {
            case '(':
                stkOprt.push(*pExpr);
                break;
            case ')':
                while ('(' != (ch = stkOprt.top()))
                {
                    *pSuff++ = ch;
                    stkOprt.pop();
                }
                stkOprt.pop();
                break;
            default:
                while (!stkOprt.empty())
                {
                    ch = stkOprt.top();
                    
                    if ('(' == ch || PrecedThan(*pExpr, ch))
                    {
                        break;
                    }
                    else
                    {
                        *pSuff++ = ch;
                        stkOprt.pop();
                    }
                }
                stkOprt.push(*pExpr);
                break;
            }//end of switch
        }//end of else
        
        pExpr++;
    }//end of while
    
    while (!stkOprt.empty())
    {
        *pSuff++ = stkOprt.top();
        stkOprt.pop();
    }
}

int Calculator(char const* suffix)
{
    char const* pExpr = suffix;
    stack<int> stkOpnd;
    
    while ('\0' != *pExpr)
    {
        if ('0' <= *pExpr && *pExpr <= '9')
        {
            stkOpnd.push(*pExpr - '0');
        }
        else
        {
            int rOpnd = stkOpnd.top();
            stkOpnd.pop();
            int lOpnd = stkOpnd.top();
            stkOpnd.pop();
            int result = 0;
            
            switch (*pExpr)
            {
            case '*':
                result = lOpnd * rOpnd;
                break;
            case '/':
                result = lOpnd / rOpnd;
                break;
            case '+':
                result = lOpnd + rOpnd;
                break;
            case '-':
                result = lOpnd - rOpnd;
                break;
            }
            
            stkOpnd.push(result);
        }
        pExpr++;
    }
    
    
    return stkOpnd.top();
}

int main(void)
{
    char const* expression = "1*2+(4-6/3)*5";
    char suffix[20] = {0};
    
    InfixToSuffix(expression, suffix);
    
    cout<< suffix <<endl;
    cout<< Calculator(suffix)<<endl;
    
    system("pause");
}
